package practice1_100;

import java.util.Arrays;

public class Practice875 {
    public int minEatingSpeed(int[] piles, int h) {
        //求piles在h时间内被一堆堆吃完，吃的速度尽可能小
        //极值piles中最大的一堆为最快速度，最小速度为1
        int maxSpeed=1;
        for (int temp:piles) {
            maxSpeed=temp>maxSpeed?temp:maxSpeed;
        }
        int minSpeed=1;
        //顺序遍历speed会超时，我们可以用二分法
//        for (int i = 1; i <maxSpeed ; i++) {
//            if(canEatOver(piles,h,i)){
//                return i;
//            }
//        }
//        return maxSpeed;
        while (minSpeed<maxSpeed){
            int midSpeed=(minSpeed+maxSpeed)/2;
            if(canEatOver(piles,h,midSpeed)){
                maxSpeed=midSpeed;
            }else {
                minSpeed=midSpeed+1;
            }
        }
        return maxSpeed;
    }
    private boolean canEatOver(int[] piles, int h, int speed) {
        for (int tempValue:piles) {
            int counthour=tempValue/speed;
            counthour+= tempValue%speed==0?0:1;
            h=h-counthour;
            if(h<0)return false;//不能在i时间吃完
        }
        return true;//能在i、时间吃完
    }


    public static void main(String[] args) {
       int a= new Practice875().minEatingSpeed(new int[]{3,6,7,11,3,5,12,4,12,7,7,3,5},20);
        System.out.println(a);
    }
}
